package com.duing.backTracking;

import java.util.ArrayList;
import java.util.List;

public class SubSetXORSum {

    public static void main(String[] args) {
        int[] nums = {5, 1, 6};
        System.out.println(subsetXORSum1(nums));
    }

    public static int subsetXORSum(int[] nums) {
        int sum = 0;
        List<Integer> result = new ArrayList<>();
        result.add(0);

        for (int num : nums) {
            // 以当前已有的子集个数为依据  处理第i+1个元素
            int size = result.size();
            for (int i = 0; i < size; i++) {
                // 先依次取出已有的子集  然后添加新的元素  构成新的子集
                Integer sub = result.get(i);
                sub ^= num;  // sub = sub ^ num
                sum += sub;
                result.add(sub);
            }
        }
        return sum;
    }


     //回溯
     //路径  选择列表  结束条件
     // result = []
     // function(路径，选择列表)
     //    if 满足结束条件   result.add(路径)  return
     //    for 选择 in 选择列表
     //       做选择
     //       function(路径下一步，选择列表)
     //       撤销选择
     //
     //{5,1,6}
     //以当前元素开头的所有子集
     //{5,1,6}  {5,1}  {5,6}  {5}
     //{1,6}  {1}
     //{6}
     //
     // 做选择  result ^= nums[cur]
     // 撤销选择   result ^= nums[cur]


    static int sum = 0;

    public static int subsetXORSum1(int[] nums) {
        dfs(0, 0, nums);
        return sum;
    }


    public static void dfs(int cur, int res, int[] nums) {
        if (cur == nums.length) {
            sum += res;
            return;
        }

        res ^= nums[cur];
        dfs(cur + 1, res, nums);
        res ^= nums[cur];
        dfs(cur + 1, res, nums);
    }
}
